package com.shm.leetcode;

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.HashMap;

/**
 * 496. 下一个更大元素 I
 * 给你两个 没有重复元素 的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。
 *
 * 请你找出 nums1 中每个元素在 nums2 中的下一个比其大的值。
 *
 * nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出 -1 。
 *
 *
 *
 * 示例 1:
 *
 * 输入: nums1 = [4,1,2], nums2 = [1,3,4,2].
 * 输出: [-1,3,-1]
 * 解释:
 *     对于 num1 中的数字 4 ，你无法在第二个数组中找到下一个更大的数字，因此输出 -1 。
 *     对于 num1 中的数字 1 ，第二个数组中数字1右边的下一个较大数字是 3 。
 *     对于 num1 中的数字 2 ，第二个数组中没有下一个更大的数字，因此输出 -1 。
 * 示例 2:
 *
 * 输入: nums1 = [2,4], nums2 = [1,2,3,4].
 * 输出: [3,-1]
 * 解释:
 *     对于 num1 中的数字 2 ，第二个数组中的下一个较大数字是 3 。
 *     对于 num1 中的数字 4 ，第二个数组中没有下一个更大的数字，因此输出 -1 。
 *
 *
 * 提示：
 *
 * 1 <= nums1.length <= nums2.length <= 1000
 * 0 <= nums1[i], nums2[i] <= 104
 * nums1和nums2中所有整数 互不相同
 * nums1 中的所有整数同样出现在 nums2 中
 *
 *
 * 进阶：你可以设计一个时间复杂度为 O(nums1.length + nums2.length) 的解决方案吗？
 * @author SHM
 */
public class NextGreaterElement {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        int n = nums2.length;
        HashMap<Integer,Integer> map = new HashMap<>(n);
        for (int i = 0; i < n; i++) {
            map.put(nums2[i],i);
        }
        int[] ans = new int[nums1.length];
        Arrays.fill(ans,-1);
        for (int i = 0; i < nums1.length; i++) {
            for (int j = map.get(nums1[i])+1; j < n; j++) {
                if (nums2[j]>nums1[i]){
                    ans[i]=nums2[j];
                    break;
                }
            }
        }
        return ans;
    }

    /**
     * 方法二：单调栈 + 哈希表
     * 思路
     *
     * 我们可以先预处理 \textit{nums}_2nums
     * 2
     * ​
     *  ，使查询 \textit{nums}_1nums
     * 1
     * ​
     *   中的每个元素在 \textit{nums}_2nums
     * 2
     * ​
     *   中对应位置的右边的第一个更大的元素值时不需要再遍历 \textit{nums}_2nums
     * 2
     * ​
     *  。于是，我们将题目分解为两个子问题：
     *
     * 第 11 个子问题：如何更高效地计算 \textit{nums}_2nums
     * 2
     * ​
     *   中每个元素右边的第一个更大的值；
     *
     * 第 22 个子问题：如何存储第 11 个子问题的结果。
     *
     * 算法
     *
     * 我们可以使用单调栈来解决第 11 个子问题。倒序遍历 \textit{nums}_2nums
     * 2
     * ​
     *  ，并用单调栈中维护当前位置右边的更大的元素列表，从栈底到栈顶的元素是单调递减的。
     *
     * 具体地，每次我们移动到数组中一个新的位置 ii，就将当前单调栈中所有小于 \textit{nums}_2[i]nums
     * 2
     * ​
     *  [i] 的元素弹出单调栈，当前位置右边的第一个更大的元素即为栈顶元素，如果栈为空则说明当前位置右边没有更大的元素。随后我们将位置 ii 的元素入栈。
     *
     * 因为题目规定了 \textit{nums}_2nums
     * 2
     * ​
     *   是没有重复元素的，所以我们可以使用哈希表来解决第 22 个子问题，将元素值与其右边第一个更大的元素值的对应关系存入哈希表。
     *
     * 细节
     *
     * 因为在这道题中我们只需要用到 \textit{nums}_2nums
     * 2
     * ​
     *   中元素的顺序而不需要用到下标，所以栈中直接存储 \textit{nums}_2nums
     * 2
     * ​
     *   中元素的值即可。
     *   复杂度分析
     *
     * 时间复杂度：O(m + n)O(m+n)，其中 mm 是 \textit{nums}_1nums
     * 1
     * ​
     *   的长度，nn 是 \textit{nums}_2nums
     * 2
     * ​
     *   的长度。我们需要遍历 \textit{nums}_2nums
     * 2
     * ​
     *   以计算 \textit{nums}_2nums
     * 2
     * ​
     *   中每个元素右边的第一个更大的值；需要遍历 \textit{nums}_1nums
     * 1
     * ​
     *   以生成查询结果。
     *
     * 空间复杂度：O(n)O(n)，用于存储哈希表。
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/next-greater-element-i/solution/xia-yi-ge-geng-da-yuan-su-i-by-leetcode-bfcoj/
     * @param nums1
     * @param nums2
     * @return
     */
    public int[] nextGreaterElement_1(int[] nums1, int[] nums2) {
        HashMap<Integer,Integer> map = new HashMap<>();
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = nums2.length-1; i >= 0 ; i--) {
            int num = nums2[i];
            while (!stack.isEmpty()&&num>=stack.peek()){
                stack.pop();
            }
            map.put(num,stack.isEmpty()?-1:stack.peek());
            stack.push(num);
        }
        int[] res = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) {
            res[i] = map.get(nums1[i]);
        }
        return res;
    }
}
